|
In dieser Arbeit werden frei partiell kommutative Monoide
(Spurmonoide) und Ersetzungssysteme über ihnen betrachtet. Diese
algebraischen Modelle zählen zu den temporalen Strukturen, mit
denen sich insbesondere Nebenläufigkeit in verteilten oder
parallelen Systemen mathematisch exakt modellieren läßt.
Ersetzungssysteme über diesen Strukturen erlauben es,
Prozeßtransformationen in nebenläufigen Kontexten zu beschreiben.
Es werden zwei Problemstellungen untersucht, das Konfluenzproblem
und das Normalformenproblem.
Wir geben einen alternativen Beweis für die Unentscheidbarkeit des
Konfluenzproblems und zeigen, daß sogar schon bei vier Buchstaben
die Konfluenz eines verkürzenden Ersetzungssystems nicht mehr
entscheidbar ist (bei einer Kommutation). Es werden verschiedene
konkrete Darstellungen von frei partiell kommutativen Monoiden
gegeben und Faktorisierungsdarstellungen der Elemente eingeführt,
die die Konstruktion von Datenstrukturen für effiziente Algorithmen
ermöglichen. Dabei führen besondere Eigenschaften der linken
Seiten eines Ersetzungssystems wie der "Zusammenhang"
aller linken Seiten oder eine "Sichtbarkeitseigenschaft"
zu effizienten Algorithmen. Es wird eine Dekompositionsmethode
entwickelt, die auf "Cographenmonoiden" führt, und mit
der der Algorithmus von Book so verallgemeinert werden kann, daß
die nicht-uniforme Zeitkomplexität linear bleibt.
|